package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import LeetCode.interview._141_Linked_List_Cycle.ListNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	Given an integer n, return the number of trailing zeroes in n!. 
　　	Note: Your solution should be in logarithmic time complexity. 
题目大意
	　给定一个整数n，求阶乘结果的尾部0的个数。 
解题思路
	考虑n!的质数因子。 
	后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数，问题就解决了。考虑下面的例子： 
	n = 5时 5!的质因子中 (2 * 2 * 2 * 3 * 5)			//1*2*3*4(分为两个2)*5
		包含一个5和三个2。因而后缀0的个数是1。 
	n = 11时 11!的质因子中(2^8 * 3^4 * 5^2 * 7)包含两个5和三个2。于是后缀0的个数就是2。 
	我们很容易观察到质因子中2的个数总是大于等于5的个数。因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢？ 
	观察15! = 有3个5(来自其中的5, 10, 15)， 所以计算n/5就可以。
		但是25! = 有6个5(有5个5来自其中的5, 10, 15, 20, 25， 另外还有1个5来自25=(5*5)的另外一个5），
			所以除了计算n/5， 还要计算n/5/5, n/5/5/5, n/5/5/5/5, …, n/5/5/5,,,/5直到商为0。
		即：25!按照之前n/5得到的是5,但是实际是6(25本身是5*5多了一个),所以25是25/5+25/5/5等于6
			同样的道理125!......................................125是125/5(25)+125/5/5(5)+125/5/5/5(1)=31
			........
				即！！！！：一路除到商为0
			
	技巧在于，每5个数会产生一个0。为什么呢？试想1*2*3*4*5*6*7*8*9*10*11，

	前5个数中有一个2一个5，相乘有一个0，后5个数中有一个10，又有一个0。以此类推，每5个数会有一个0。
	
 * @Date 2017-09-14 20：59
 */
public class _172_Factorial_Trailing_Zeroes {
   
    public int trailingZeroes(int n) {
    	int sum = 0;
    	while (n > 0) {
    		sum += n / 5;		//每5个一个0
    		n = n / 5;
    	}
    	return sum;
    }

	public static void main(String[] args) {
		_172_Factorial_Trailing_Zeroes obj = new _172_Factorial_Trailing_Zeroes();
		LogUtils.println("结果", obj.trailingZeroes(125));
	}

}
